package com.cqs.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Author:li
 * <p>
 * create date: 18-6-1 19:08
 */
public class GenerateParentheses22 {
    private List<String> list = new ArrayList<>();

    private int n;

    //3ms
    public List<String> generateParenthesis(int n) {
        this.n = n;
        //回溯法常用到递归 本质就全遍历 遍历过程中会去掉不符合条件的分支
        next("", 0, 0);
        return list;
    }

    /**
     * 用两个指针去掉不符合要求的分支
     *
     * @param str
     * @param left
     * @param right
     */
    private void next(final String str, int left, int right) {
        if (str.length() == (n << 1)) {//终止条件
            list.add(str);
        } else {
            if (left < right) {
                throw new RuntimeException();
            }
            if (left < n) {
                next(str + "(", 1 + left, right);
            }
            if (left > right) {
                next(str + ")", left, 1 + right);
            }
        }
    }

    public static void main(String[] args) {
        GenerateParentheses22 gp = new GenerateParentheses22();
        System.out.println(gp.generateParenthesis(3));
    }

    //1ms
    private static class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> allStr = new ArrayList<String>();
            gP(n, n, new char[2 * n], allStr);
            return allStr;

        }

        public void gP(int a, int b, char[] str, List<String> allStr) {
            if (a == 0) {
                while (b > 0) {
                    str[str.length - b] = ')';
                    b--;
                }

                allStr.add(String.valueOf(str));
            } else {
                int n = str.length - (a + b);
                if (a < b) {
                    str[n] = '(';
                    gP(a - 1, b, str, allStr);
                    str[n] = ')';
                    gP(a, b - 1, str, allStr);
                } else {
                    str[n] = '(';
                    gP(a - 1, b, str, allStr);
                }
            }
        }
    }
}
